package tianhao.luo.linkedlist;

/**
 * 单向环形链表
 *
 * @author: tianhao.luo@hand-china.com 2021/6/15  10:41
 */
public class CircleSingleLinkedList {
    private JosepfuNode first = new JosepfuNode(-1);


    /**
     * 创建环形链表
     *
     * @param nums 环形链表的长度
     */
    public void createList(int nums) {

        if (nums < 1) {
            System.out.println("nums的值不正确");
            return;
        }

        // temp始终指向环形链表的最后一个节点,方便我们做新增节点的处理
        JosepfuNode temp = null;
        // 创建环形链表
        for (int i = 1; i <= nums; i++) {
            JosepfuNode node = new JosepfuNode(i);

            if (i == 1) {
                // 第一个节点
                // first的next需要指向新加入节点;新加入节点的next需要指向node
                first.next = node;
                node.next = node;
                temp = node;
            } else {
                // 加入节点
                // 新加入节点的next需要指向first.next,原最后一个节点temp的next需要指向新加入节点;同时temp指向新加入节点
                node.next = first.next;
                temp.next = node;
                temp = node;
            }
        }
    }

    /**
     * 加入一个节点
     *
     * @param node 节点
     */
    public void addBoy(JosepfuNode node) {
        if (first.next == null) {
            // 链表为空
            // 加入的节点就是第一个节点,并形成环
            first.next = node;
            node.next = node;
            return;
        }

        JosepfuNode temp = first;

        while (true) {
            // 找出末尾节点
            // 节点.next == first
            if (temp.next == first) {
                // 结尾了
                // 末尾节点的next指向新加入节点,新加入节点next指向first
                temp.next = node;
                node.next = first;
                break;
            }
            // 没找见就后移
            temp = temp.next;
        }
    }


    /**
     * 列出所有节点信息
     */
    public void list() {
        if (first.next == null) {
            System.out.println("空链表");
            return;
        }
        JosepfuNode temp = first.next;

        while (true) {
            // 结尾:当前节点的next指向first.next
            System.out.printf("当前节点内容:%d\n", temp.no);
            if (temp.next == first.next) {
                break;
            }
            temp = temp.next;
        }
    }


    /**
     * 问题:设编号为1,2,...n的n个人围坐一圈,约定编号为k(1<=k<=n)的人从1开始报数,数到countNum的那个人出列,
     * 它的下一位又从1开始报数,数到countNum的那个人又出列,一次类推,直到所有人出列为止,由此产生一个出队编号的序列.
     *
     * 需要一个temp节点,用它作为链表的最后一个节点的拷贝;方便我们判断链表中是否移除完毕(temp = first.next)
     * 节点报数前,先让first和temp移动 k -1 次
     * 当节点报数时,让first指针和temp节点同时移动countNum-1次
     * 将first.next指向的节点出圈
     * @param startNo 从第几个小孩开始数
     * @param countNum 数几次
     * @param nums 最初有多少个在其中
     */
    public void outOfCircle(int startNo,int countNum,int nums) {
        if (first == null || startNo<1 || startNo>nums){
            System.out.println("参数输入有误");
            return;
        }
        // temp是链表中最后一个元素的副本
        JosepfuNode temp = first.next;
        while (true) {
            // 当前节点的next指向了first,表示这就是最后一个元素
            if (temp.next == first.next) {
                break;
            }
            temp = temp.next;
        }

        // 报数前,让first和helper移动k-1次
        for (int i = 0; i < startNo - 1; i++) {
            first = first.next;
            temp = temp.next;
        }

        while (true){
            if (temp == first.next){
                // 只有一个节点
                break;
            }
            // temp:链表最后一个元素的副本
            // first:指向链表中第一个元素,并不是链表中的元素
            // 因为报数是要从自己开始报数,自己报1也算一次,总共报countNum次,就是要让first和temp移动countNum-1次
            // delEle为将被移除的元素,它需要从first.next开始计算,因为first不是实际的数据元素,它只是next指向了第一个元素
            JosepfuNode delEle = first.next;
            for (int i = 0; i < countNum-1; i++) {
                delEle = delEle.next;
                // 尾部节点同时后移
                temp = temp.next;
            }

            // 此时delEle指向的节点,就是要出圈的节点
            System.out.printf("出圈节点:%d\n",delEle.getNo());
            // 此时让first指针后移,让他的next指向被移除节点的next
            // 同时更新temp.next指向新的节点
            first = delEle;
            temp.next = delEle.next;
        }
        System.out.printf("最后留下来的节点:%d\n",temp.no);
    }
}
